#include <iostream>
#include<sys/time.h>
#include<unistd.h>
using namespace std;
int* a, * b;
const int n = 300000;//规定是偶数，方便二路算法计算
void recursion(int n)
{
    if (n == 1)
        return;
    else
    {
        for (int i = 0; i < n; i++)
            a[i] += a[n - i - 1];
        n = n / 2;
        recursion(n);
    }
}


int main()
{
    a = new int [n];
    b = new int[n];
    //初始化记录数据的数组
    for (int i = 0; i < n; i++)
    {
        a[i] = rand() % 100;
        b[i] = a[i];
    }
    //多链路是算法
    int solution2 = 0;
    int* solution22 = new int[2];
    solution22[0] = 0;
    solution22[1] = 0;

    struct timeval start2;
    struct timeval end2;
    gettimeofday(&start2, NULL);
    for (int i = 0; i < n-1; i = i+2)
    {
        solution22[0] += a[i];
        solution22[1] += a[i+1];
    }
    solution2 = solution22[0] + solution22[1];
    gettimeofday(&end2, NULL);
    cout << "多链路式: " << end2.tv_sec - start2.tv_sec << "ms" << endl;


    //普通算法
    int solution1 = 0;
    struct timeval start1;
    struct timeval end1;
    gettimeofday(&start1, NULL);
    for (int i = 0; i < n; i++)
        solution1 += a[i];
    gettimeofday(&end1, NULL);
    cout << "普通算法耗时: " << end1.tv_sec - start1.tv_sec << "ms" << endl;



    //递归算法
    struct timeval start3;
    struct timeval end3;
    gettimeofday(&start3, NULL);
    recursion(n);
    gettimeofday(&end3, NULL);
    cout << "递归算法耗时: " << end3.tv_sec - start3.tv_sec << "ms" << endl;

    //二重循环
    struct timeval start4;
    struct timeval end4;
    gettimeofday(&start4, NULL);
    for (int m = n; m > 1; m /= 2)
        for (int i = 0; i < m / 2; i++)
            a[i] = a[i * 2] + a[i * 2 + 1];
    gettimeofday(&end4, NULL);
    cout << "二重循环耗时: " << end4.tv_sec - start4.tv_sec << "ms" << endl;

}